In the

mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

area of

graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, an induced path in an

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ve ...

is a

path A path is a route for physical travel – see Trail. Path or PATH may also refer to: Physical paths of different types * Bicycle path * Bridle path, used by people on horseback * Course (navigation), the intended path of a vehicle * Desire p ...

that is an

induced subgraph In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset. Defini ...

of . That is, it is a sequence of vertices in such that each two adjacent vertices in the sequence are connected by an edge in , and each two nonadjacent vertices in the sequence are not connected by any edge in . An induced path is sometimes called a snake, and the problem of finding long induced paths in

hypercube graph In graph theory, the hypercube graph is the graph formed from the vertices and edges of an -dimensional hypercube. For instance, the cube graph is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. has vertices, e ...

s is known as the

snake-in-the-box The snake-in-the-box problem in graph theory and computer science deals with finding a certain kind of path along the edges of a hypercube. This path starts at one corner and travels along the edges to as many corners as it can reach. After it g ...

problem. Similarly, an induced cycle is a cycle that is an induced subgraph of ; induced cycles are also called chordless cycles or (when the length of the cycle is four or more) holes. An antihole is a hole in the

complement A complement is something that completes something else. Complement may refer specifically to: The arts * Complement (music), an interval that, when added to another, spans an octave ** Aggregate complementation, the separation of pitch-clas ...

of , i.e., an antihole is a complement of a hole. The length of the longest induced path in a graph has sometimes been called the detour number of the graph; for

sparse graph In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges (where every pair of vertices is connected by one edge). The opposite, a graph with only a few edges, is a sparse graph. The distinction ...

s, having bounded detour number is equivalent to having bounded tree-depth. The induced path number of a graph is the smallest number of induced paths into which the vertices of the graph may be partitioned, and the closely related path cover number of is the smallest number of induced paths that together include all vertices of . The girth of a graph is the length of its shortest cycle, but this cycle must be an induced cycle as any chord could be used to produce a shorter cycle; for similar reasons the odd girth of a graph is also the length of its shortest odd induced cycle.

Example

The illustration shows a cube, a graph with eight vertices and twelve edges, and an induced path of length four in this graph. A straightforward case analysis shows that there can be no longer induced path in the cube, although it has an induced cycle of length six. The problem of finding the longest induced path or cycle in a hypercube, first posed by , is known as the

problem, and it has been studied extensively due to its applications in coding theory and engineering.

Characterization of graph families

Many important graph families can be characterized in terms of the induced paths or cycles of the graphs in the family. * Trivially, the connected graphs with no induced path of length two are the

complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is ...

s, and the connected graphs with no induced cycle are the

tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...

s. * A

triangle-free graph In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with g ...

is a graph with no induced cycle of length three. * The

cograph In graph theory, a cograph, or complement-reducible graph, or ''P''4-free graph, is a graph that can be generated from the single-vertex graph ''K''1 by complementation and disjoint union. That is, the family of cographs is the smallest class of ...

s are exactly the graphs with no induced path of length three. * The

chordal graph In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a ''chord'', which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced c ...

s are the graphs with no induced cycle of length four or more. * The even-hole-free graphs are the graphs containing no induced cycles with an even number of vertices. * The

trivially perfect graph In graph theory, a trivially perfect graph is a graph with the property that in each of its induced subgraphs the size of the maximum independent set equals the number of maximal cliques. Trivially perfect graphs were first studied by but were na ...

s are the graphs that have neither an induced path of length three nor an induced cycle of length four. * By the strong perfect graph theorem, the

perfect graph In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the order of the largest clique of that subgraph (clique number). Equivalently stated in symbolic terms an arbitrary graph G=(V,E) is perfe ...

s are the graphs with no odd hole and no odd antihole. * The

distance-hereditary graph In graph theory, a branch of discrete mathematics, a distance-hereditary graph (also called a completely separable graph) is a graph in which the distances in any connected induced subgraph are the same as they are in the original graph. Thus, any ...

s are the graphs in which every induced path is a shortest path, and the graphs in which every two induced paths between the same two vertices have the same length. * The

block graph In graph theory, a branch of combinatorial mathematics, a block graph or clique tree. is a type of undirected graph in which every biconnected component (block) is a clique. Block graphs are sometimes erroneously called Husimi trees (after K� ...

s are the graphs in which there is at most one induced path between any two vertices, and the connected block graphs are the graphs in which there is exactly one induced path between every two vertices.

Algorithms and complexity

It is NP-complete to determine, for a graph ''G'' and parameter ''k'', whether the graph has an induced path of length at least ''k''. credit this result to an unpublished communication of

Mihalis Yannakakis Mihalis Yannakakis ( el, Μιχάλης Γιαννακάκης; born 13 September 1953 in Athens, Greece)independent sets in graphs, by the following reduction. From any graph ''G'' with ''n'' vertices, form another graph ''H'' with twice as many vertices as ''G'', by adding to ''G'' ''n''(''n'' − 1)/2 vertices having two neighbors each, one for each pair of vertices in ''G''. Then if ''G'' has an independent set of size ''k'', ''H'' must have an induced path and an induced cycle of length 2''k'', formed by alternating vertices of the independent set in ''G'' with vertices of ''I''. Conversely, if ''H'' has an induced path or cycle of length ''k'', any maximal set of nonadjacent vertices in ''G'' from this path or cycle forms an independent set in ''G'' of size at least ''k''/3. Thus, the size of the maximum independent set in ''G'' is within a constant factor of the size of the longest induced path and the longest induced cycle in ''H''. Therefore, by the results of on inapproximability of independent sets, unless NP=ZPP, there does not exist a polynomial time algorithm for approximating the longest induced path or the longest induced cycle to within a factor of O(''n''^1/2-ε) of the optimal solution. Holes (and antiholes in graphs without chordless cycles of length 5) in a graph with n vertices and m edges may be detected in time (n+m²).

Atomic cycles

Atomic cycles are a generalization of chordless cycles, that contain no ''n''-chords. Given some cycle, an ''n''-chord is defined as a path of length ''n'' connecting two points on the cycle, where ''n'' is less than the length of the shortest path on the cycle connecting those points. If a cycle has no ''n''-chords, it is called an atomic cycle, because it cannot be decomposed into smaller cycles.. In the worst case, the atomic cycles in a graph can be enumerated in O(''m''²) time, where ''m'' is the number of edges in the graph.

Notes

References

* * * * * * * * * * * * * {{refend Graph theory objects